package com.linyaonan.leetcode.medium._2789;

import java.util.LinkedList;

/**
 * 给你一个下标从 0 开始、由正整数组成的数组 nums 。
 * <p>
 * 你可以在数组上执行下述操作 任意 次：
 * <p>
 * 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。
 * 返回你可以从最终数组中获得的 最大 元素的值。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [2,3,7,9,3]
 * 输出：21
 * 解释：我们可以在数组上执行下述操作：
 * - 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
 * - 选中 i = 1 ，得到数组 nums = [5,16,3] 。
 * - 选中 i = 0 ，得到数组 nums = [21,3] 。
 * 最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。
 * 示例 2：
 * <p>
 * 输入：nums = [5,3,3]
 * 输出：11
 * 解释：我们可以在数组上执行下述操作：
 * - 选中 i = 1 ，得到数组 nums = [5,6] 。
 * - 选中 i = 0 ，得到数组 nums = [11] 。
 * 最终数组中只有一个元素，即 11 。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 10^5
 * 1 <= nums[i] <= 10^6
 *
 * @author: Lin
 * @date: 2024/3/14
 */
public class LargestElementInAnArrayAfterMergeOperations {

    /**
     * 单调栈的思路，如果压入栈的数据比栈顶数据大或者等于则进行合并压入栈，直到栈顶数据大于后退出
     *
     * @param nums
     * @return
     */
    public long maxArrayValue(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        // 遍历索引
        int index = nums.length - 1;
        LinkedList<Long> stack = new LinkedList<>();
        stack.addLast((long) nums[index]);
        index--;

        while (!stack.isEmpty() && index >= 0) {
            Long top = stack.getLast();
            int add = nums[index];
            if (add <= top) {
                stack.addLast(stack.removeLast() + add);
            } else {
                stack.addLast((long) add);
            }
            index--;
        }

        long max = -1;
        for (int i = 0; i < stack.size(); i++) {
            max = Math.max(max, stack.get(i));
        }

        return max;
    }

}
